home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Caml Light 0.61 / Source / src / lib / baltree.mli < prev    next >
Encoding:
Text File  |  1993-09-24  |  4.3 KB  |  79 lines  |  [TEXT/MPS ]
  1. (* Basic balanced binary trees *)
  2.  
  3. (* This module implements balanced ordered binary trees.
  4.    All operations over binary trees are applicative (no side-effects).
  5.    The [set] and [map] modules are based on this module.
  6.    This modules gives a more direct access to the internals of the
  7.    binary tree implementation than the [set] and [map] abstractions,
  8.    but is more delicate to use and not as safe. For advanced users only. *)
  9.  
  10. type 'a t = Empty | Node of 'a t * 'a * 'a t * int;;
  11.         (* The type of trees containing elements of type ['a].
  12.            [Empty] is the empty tree (containing no elements). *)
  13.  
  14. type 'a contents = Nothing | Something of 'a;;
  15.         (* Used with the functions [modify] and [split], to represent
  16.            the presence or the absence of an element in a tree. *)
  17.  
  18. value add: ('a -> int) -> 'a -> 'a t -> 'a t
  19.         (* [add f x t] inserts the element [x] into the tree [t].
  20.            [f] is an ordering function: [f y] must return [0] if
  21.            [x] and [y] are equal (or equivalent), a negative integer if
  22.            [x] is smaller than [y], and a positive integer if [x] is
  23.            greater than [y]. The tree [t] is returned unchanged if
  24.            it already contains an element equivalent to [x] (that is,
  25.            an element [y] such that [f y] is [0]).
  26.            The ordering [f] must be consistent with the orderings used
  27.            to build [t] with [add], [remove], [modify] or [split]
  28.            operations. *)
  29.   and contains: ('a -> int) -> 'a t -> bool
  30.         (* [contains f t] checks whether [t] contains an element
  31.            satisfying [f], that is, an element [x] such
  32.            that [f x] is [0]. [f] is an ordering function with the same
  33.            constraints as for [add]. It can be coarser (identify more
  34.            elements) than the orderings used to build [t], but must be
  35.            consistent with them. *)
  36.   and find: ('a -> int) -> 'a t -> 'a
  37.         (* Same as [contains], except that [find f t] returns the element [x]
  38.            such that [f x] is [0], or raises [Not_found] if none has been
  39.            found. *)
  40.   and remove: ('a -> int) -> 'a t -> 'a t
  41.         (* [remove f t] removes one element [x] of [t] such that [f x] is [0].
  42.            [f] is an ordering function with the same constraints as for [add].
  43.            [t] is returned unchanged if it does not contain any element
  44.            satisfying [f]. If several elements of [t] satisfy [f],
  45.            only one is removed. *)
  46.   and modify: ('a -> int) -> ('a contents -> 'a contents) -> 'a t -> 'a t
  47.         (* General insertion/modification/deletion function.
  48.            [modify f g t] searchs [t] for an element [x] satisfying the
  49.            ordering function [f]. If one is found, [g] is applied to
  50.            [Something x]; if [g] returns [Nothing], the element [x]
  51.            is removed; if [g] returns [Something y], the element [y]
  52.            replaces [x] in the tree. (It is assumed that [x] and [y]
  53.            are equivalent, in particular, that [f y] is [0].)
  54.            If the tree does not contain any [x] satisfying [f],
  55.            [g] is applied to [Nothing]; if it returns [Nothing],
  56.            the tree is returned unchanged; if it returns [Something x],
  57.            the element [x] is inserted in the tree. (It is assumed that
  58.            [f x] is [0].) The functions [add] and [remove] are special cases
  59.            of [modify], slightly more efficient. *)
  60.   and split: ('a -> int) -> 'a t -> 'a t * 'a contents * 'a t
  61.         (* [split f t] returns a triple [(less, elt, greater)] where
  62.            [less] is a tree containing all elements [x] of [t] such that
  63.            [f x] is negative, [greater] is a tree containing all
  64.            elements [x] of [t] such that [f x] is positive, and [elt]
  65.            is [Something x] if [t] contains an element [x] such that
  66.            [f x] is [0], and [Nothing] otherwise. *)
  67.   and compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int
  68.         (* Compare two trees. The first argument [f] is a comparison function
  69.            over the tree elements: [f e1 e2] is zero if the elements [e1] and 
  70.            [e2] are equal, negative if [e1] is smaller than [e2],
  71.            and positive if [e1] is greater than [e2]. [compare f t1 t2]
  72.            compares the fringes of [t1] and [t2] by lexicographic extension
  73.            of [f]. *)
  74. (*--*)
  75.   and join: 'a t -> 'a -> 'a t -> 'a t
  76.   and concat: 'a t -> 'a t -> 'a t
  77. ;;
  78.  
  79.